Mathematical Muffin Morsels: Nobody wants a Small Piece by William Gasarch Erik Metz Jacob Prinz and Daniel Smolyak
Author:William Gasarch, Erik Metz, Jacob Prinz and Daniel Smolyak
Language: eng
Format: epub
Publisher: World Scientific Publishing Co. Pte. Ltd.
Published: 2020-07-15T00:00:00+00:00
Chapter 10
The Easy Buddy–Match Method
10.1.Recap and Goals for This Chapter
From Chapters 4, 6, and 8 we know that, for m ≥ s,
Just for now we will refer to the min of those quantities as minf(m, s). Is it the case that, for all m ≥ s, f(m, s) = minf(m, s)? No. The counterexample with the smallest s is f(16, 15); however it is more illustrative to show the following:
(The first two results can be obtained by MID.)
The proof of the upper bounds uses a technique, which we call easy buddy–match (EBM). We develop an algorithm EBM(m, s) which, given m, s, outputs an α such that f(m, s) ≤ α. It only works when there are 2-shares (so V = 3). The key new idea is that if Alice is a 2-student and she has a share of size x, then her other share has size − x. This is called matching. It is similar to buddying where, if there is a share of size x, there is a share of size 1 − x.
Exercise 10.1. For (m, s) = (16, 15), (17, 16), (19, 18), (29, 27):
(1)Compute α = minf(m, s).
(2)Compute FINDPROC(m, s, α). (You should get a DK which means that minf(m, s) is unlikely to be f(m, s).)
Download
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.
The Infinite Retina by Robert Scoble Irena Cronin(5346)
Harry Potter and the Cursed Child: The Journey by Harry Potter Theatrical Productions(4300)
The Sports Rules Book by Human Kinetics(4057)
Molly's Game: From Hollywood's Elite to Wall Street's Billionaire Boys Club, My High-Stakes Adventure in the World of Underground Poker by Molly Bloom(3321)
A Knight of the Seven Kingdoms by George R R Martin(3014)
Quidditch Through the Ages by J.K. Rowling(2982)
How To by Randall Munroe(2902)
Quidditch Through the Ages by J K Rowling & Kennilworthy Whisp(2869)
Quidditch Through the Ages by Kennilworthy Whisp by J.K. Rowling(2742)
Flowers For Algernon by Daniel Keyes(2718)
Quidditch through the Ages by J. K. Rowling(2690)
Stacked Decks by The Rotenberg Collection(2670)
Quidditch Through The Ages by J. K. Rowling(2656)
776 Stupidest Things Ever Said by Ross Petras(2572)
What If?: Serious Scientific Answers to Absurd Hypothetical Questions by Randall Munroe(2536)
Ready Player One: A Novel by Ernest Cline(2531)
Beautiful Oblivion by Jamie McGuire(2452)
The Book of Questions: Revised and Updated by Gregory Stock Ph.d(2433)
Champions of Illusion by Susana Martinez-Conde & Stephen Macknik(2318)
